package com.demo.study.algorithm.search;

/**
 * 斐波那契数列
 * 求斐波那契数列第n项的值
 *
 * @author Baymax
 * @since 2024-08-13
 */
public class A04_Fibonacci_Case {
    public static void main(String[] args) {
        System.out.println("兔子数量：" + CaseRabbitCount.fibonacciRabbit(5));
        System.out.println("爬楼梯方法数：" + CaseStaircaseCount.staircaseCount(5));
    }

    /**
     * 斐波那契-兔子问题
     */
    static class CaseRabbitCount {
        public static int fibonacciRabbit(int month) {
            if (month < 1) {
                return 0;
            }
            return doFibonacciRabbit(month) * 2;
        }

        private static int doFibonacciRabbit(int month) {
            if (month == 1) {
                return 1;
            }
            if (month == 2) {
                return 1;
            }
            return doFibonacciRabbit(month - 1) + doFibonacciRabbit(month - 2);
        }
    }

    /**
     * 斐波那契-楼梯台阶多少种走法问题
     */
    static class CaseStaircaseCount {
        public static int staircaseCount(int step) {
            if (step < 1) {
                return 0;
            }
            return doStaircaseCount(step);
        }

        private static int doStaircaseCount(int step) {
            if (step == 1) {
                return 1;
            }
            if (step == 2) {
                return 2;
            }
            return doStaircaseCount(step - 1) + doStaircaseCount(step - 2);
        }
    }
}